package leetcode.code0368;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution7 implements IDebug {

	public List<Integer> largestDivisibleSubset(int[] nums) {
		Arrays.sort(nums);
		int len = nums.length;
		Integer[] nexts = new Integer[len];
		int[] seqs = new int[len];
		int p = 0;
		nexts[p] = null;
		seqs[p] = 1;
		p++;
		int max = 1;
		Integer maxpos = 0;
		for (int i = 1; i < len; i++) {
			int cur = nums[i];
			Integer curNext = null;
			int curSeq = 1;
			for (int j = p - 1; j >= 0; j--) {
				int valp = nums[j];
				int seqp = seqs[j];
				if (cur % valp == 0 && seqp >= curSeq) {
					curSeq = seqp + 1;
					curNext = j;
				}
			}
			nexts[p] = curNext;
			seqs[p] = curSeq;
			if (curSeq > max) {
				max = curSeq;
				maxpos = p;
			}
			p++;
		}
		List<Integer> ans = new ArrayList<>();
		while (maxpos != null) {
			ans.add(nums[maxpos]);
			maxpos = nexts[maxpos];
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<Integer> ans = HelpDebug.str2intlist("[9,18,90,180,360,720]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[5,9,18,54,108,540,90,180,360,720]")));

	}

	@Override
	public void debug2() {
		List<Integer> ans = HelpDebug.str2intlist("[4,8,16]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[3,4,16,8]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		List<Integer> ans = HelpDebug.str2intlist("[2,4,8]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[2,3,4,8]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		List<Integer> ans = HelpDebug.str2intlist("[4,8,16,32]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[3,4,6,8,12,16,32]")));

	}

	public static void main(String[] args) {
		Solution7 so = new Solution7();
		so.debug4();
//		so.debug1();
//		so.debug2();
//		so.debug3();

	}

}
